//
//  ProblemOffer49.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/22.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 49. 丑数
 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 示例:
     输入: n = 10
     输出: 12
     解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 说明:
     1 是丑数。
     n 不超过1690。
 */
@objcMembers class ProblemOffer49: NSObject {
    func solution() {
        print(nthUglyNumber(10))
    }
    
    /*
     丑数是：都是由2、3、5 相乘得到的；
     那么我们可以让一个数*2、*3、*5，开始推算
     例如取一个最小的丑数1：
     1*2 = 2
     1*3 = 3
     1*5 = 5
     那么下一个丑数就是2，现在的丑数列表：[1, 2]; 我们按照这个思路，可以一步一步的推算出下一个丑数, 然后添加到列表中
     
     现在问题是：1*2=2，那么后面1变成哪个数，可以继续进行判断呢？
     答案是2，这不是简单的+1，而是丑数数组[1, 2]里面 1后面的那个丑数，因为丑数都必须是2、3、5组成
     
     简单列一下：下面几次的判断
     2*2 = 4
     1*3 = 3
     1*5 = 5
     这里其他2次还是1，因为3和5目前没有添加到丑数列表中，所以还是1
     最小值是3，添加到列表中：[1, 2, 3], 那么1*3的1按照丑数列表就变成了2，下一次：
     2*2 = 4
     2*3 = 6
     1*5 = 5
     最小值：4，添加，[1, 2, 3, 4], 2按照丑数列表就变成3，下一次：
     3*2 = 6
     2*3 = 6
     1*5 = 5
     最小值是5，添加，[1, 2, 3, 4, 5], 1按照丑数列表就变成2，下一次：
     3*2 = 6
     2*3 = 6
     2*5 = 10
     最小值是6，添加，[1, 2, 3, 4, 5, 6], 这里有2个6，所以都要往后延一位。下一次：
     4*2 = 8
     3*3 = 9
     2*5 = 10
     。。。。。。。
     */
    func nthUglyNumber(_ n: Int) -> Int {
        if n == 1 {
            return 1
        }
        
        // 丑数列表
        var list: [Int] = [1]
        // 定义3个变量，都指向数组的0的位置
        var ai = 0, bi = 0, ci = 0
        
        while list.count < n {
            let aValue = 2 * list[ai], bValue = 3 * list[bi], cValue = 5 * list[ci]
            // 求出最小值
            list.append(min(aValue, bValue, cValue))
            
            // 让最小值的index往后走一位
            if list.last! == aValue {
                ai += 1
            }
            if list.last! == bValue {
                bi += 1
            }
            if list.last! == cValue {
                ci += 1
            }
        }
        print(list)
        return list.last!
    }
}
